package offer;

import java.util.Stack;

/**
 * Creared with IntelliJ IDEA.
 * Description:给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 * User:yxd
 * Date:2022-08-12
 * Time:10:00
 */
public class BM44 {
    public boolean isValid (String s) {
        // write code here
        //不是有效括号数
        if(s.length() % 2  != 0)return false;
        Stack<Character> stack = new Stack<>();
        for(int i = 0;i < s.length(); i++){
            if(s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '['){
                stack.add(s.charAt(i));
            }else{
                if(!stack.isEmpty() && ((s.charAt(i) == ')' && stack.peek() == '(')
                        || (s.charAt(i) == '}' && stack.peek() == '{')
                        || (s.charAt(i) == ']' && stack.peek() == '['))){
                    stack.pop();
                }else{
                    //括号不匹配
                    return false;
                }
            }

        }
        //有多余的括号
        return stack.isEmpty();
    }
}
